/**
 * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 * 
 * 思路：Floyd 算法（快慢指针）
 * 1. 使用快慢指针找到相遇点
 * 2. 找到相遇点后，让一个指针从头开始，另一个从相遇点开始，同时移动
 * 3. 它们相遇的地方就是环的入口
 * 
 * 数学证明：
 * - 设从头到入口的距离为 a，环的长度为 b
 * - 快指针走了 f 步，慢指针走了 s 步
 * - 快指针速度是慢指针的2倍：f = 2s
 * - 快指针比慢指针多走了 n 圈：f = s + nb
 * - 联立得：s = nb, f = 2nb
 * - 慢指针再走 a 步就到入口，此时从头指针也走 a 步，正好在入口相遇
 */
function ListNode(val) {
  this.val = val
  this.next = null
}

function detectCycle(head) {
  let slow = head
  let fast = head
  
  while(fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
    if(slow === fast) {
      let ptr = head
      while(ptr !== slow) {
        ptr = ptr.next
        slow = slow.next
      }
      return ptr 
    }
  }
  return null
}

const head = [3,2,0,-4]
console.log(detectCycle(head))
/**
idea: 先找到相遇点，然后让一个指针从头开始，另一个从相遇点开始，同时移动，直到相遇，相遇的地方就是环的入口
 */